from typing import List


class DSU:
    def __init__(self, n: int):
        self._n = n
        self._array = [i for i in range(n)]
        self._size = [1] * n

        self.group_num = n  # 连通分支数量

    def find(self, i: int) -> int:
        if self._array[i] != i:
            self._array[i] = self.find(self._array[i])
        return self._array[i]

    def union(self, i: int, j: int) -> bool:
        i, j = self.find(i), self.find(j)
        if i != j:
            if self._size[i] >= self._size[j]:
                self._array[j] = i
                self._size[i] += self._size[j]
            else:
                self._array[i] = j
                self._size[j] += self._size[i]
            self.group_num -= 1
            return True
        else:
            return False

    def is_connected(self, i: int, j: int) -> bool:
        return self.find(i) == self.find(j)


class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        size = len(strs)
        length = len(strs[0])

        dsu = DSU(size)

        def check(a: str, b: str) -> bool:
            """判断a和b是否相似"""
            num = 0
            for ii in range(length):
                if a[ii] != b[ii]:
                    num += 1
                    if num > 2:
                        return False
            return True

        for i in range(size):
            for j in range(i + 1, size):
                if dsu.find(i) != dsu.find(j):
                    if check(strs[i], strs[j]):
                        dsu.union(i, j)

        return dsu.group_num


if __name__ == "__main__":
    print(Solution().numSimilarGroups(["tars", "rats", "arts", "star"]))  # 2
    print(Solution().numSimilarGroups(["omv", "ovm"]))  # 1
